A number of systems and programs are offered on the market for the design, the engineering and the manufacturing of objects. CAD is an acronym for Computer-Aided Design, e.g. it relates to software solutions for designing an object. CAE is an acronym for Computer-Aided Engineering, e.g. it relates to software solutions for simulating the physical behavior of a future product. CAM is an acronym for Computer-Aided Manufacturing, e.g. it relates to software solutions for defining manufacturing processes and operations. In such computer-aided design systems, the graphical user interface plays an important role as regards the efficiency of the technique. These techniques may be embedded within Product Lifecycle Management (PLM) systems. PLM refers to a business strategy that helps companies to share product data, apply common processes, and leverage corporate knowledge for the development of products from conception to the end of their life, across the concept of extended enterprise. The PLM solutions provided by Dassault Systèmes (under the trademarks CATIA, ENOVIA and DELMIA) provide an Engineering Hub, which organizes product engineering knowledge, a Manufacturing Hub, which manages manufacturing engineering knowledge, and an Enterprise Hub which enables enterprise integrations and connections into both the Engineering and Manufacturing Hubs. All together the system delivers an open object model linking products, processes, resources to enable dynamic, knowledge-based product creation and decision support that drives optimized product definition, manufacturing preparation, production and service.
Such systems may deal with industrializing a mechanical part represented by a virtual solid model. The industrialization may be to design the shape of the mold that is supposed to produce said part. One step to perform this industrialization is often to recognize and remove (from the input solid) details that are not produced by the molding process. These details may include holes. An issue can thus be to compute the topological invariants of a given input object according to the following meaning. A goal is to localize topological features of interest. When the input object is an image, a topological feature is a hole. When the input object is a solid, a topological feature is a tunnel (synonym for “through hole”) or a handle.
From the mathematical point of view, there is no limit in the dimension of objects under study. Nevertheless, industrial algorithms deal with 2D images or 3D solids. Algorithms to recognize holes in a 2D image are designed on purpose and cannot be generalized to solids. Algorithms to automatically recognize tunnels and handles on a solid can be classified into two categories. The first one makes use of iterative matrix computations in order to get the Smith normal form of the boundary matrix representing the topology of the input object. The so-called homology generators can be easily read on the Smith normal form matrix. From these generators, tunnels and handles can be determined. A typical reference is An iterative algorithm for homology computation on simplicial shapes, D. Boltcheva, D. Canino, S. M. Aceituno, J. C. Léon, L. De Floriani, F. Hétroy, CAD, 43, 11 (2011) 1457-1467. The second category of algorithms performs computations on simplicial complexes. In short, a 2D simplicial complex is a triangulated graph and a 3D simplicial complex is tetrahedral mesh of a volume. A typical reference is Computing geometry-aware handle and tunnel loops in 3D models, T. K. Dey, K. Li, J. Sun, D. Cohen-Steiner, ACM Transactions on Graphics (TOG)—Proceedings of ACM SIGGRAPH 2008, Volume 27 Issue 3, August 2008. Commercial CAD systems also provide part simplification capabilities. They are semi-automatic in the sense that the user is supposed to select faces of the detail to remove and the system sometimes completes this selection by a local recognition. This process manages through holes as well.
This prior art has several drawbacks. Computing the Smith normal form matrix of a boundary matrix is questionable for the following reason. Coefficients of the boundary matrix are 0 and 1 but its size can be very large. Coefficients of the Smith normal form are integer numbers. They are obtained through an iterative algorithm that performs integer arithmetic computations, and intermediate results may involve large integer numbers. As opposed to floating numbers, there is no memory upper bound to represent an arbitrary large integer number in a computer. For this reason, failure cannot be excluded when computing the Smith normal form of a boundary matrix. This makes the Smith normal form technology incompatible with the industrial domain where input objects of any size must be taken into account. The second reference computes tunnels and handles of a solid model, but a drawback is that it requires a Voronoï triangulation of the B-Rep of the solid, a Voronoï 3D meshing of the inside volume of the solid and a Voronoï 3D meshing of the outside volume of the solid. In other words, the solid itself and its 3D spatial neighborhood must be meshed. Firstly, such a computation may fail because of the complexity of the meshing algorithm and the input geometry. Secondly, the computing time for meshing and topological computations is not compatible with an interactive use. Existing semi-automatic solutions of commercial CAD systems are not satisfactory because of their weak productivity.
Within this context, there is still a need for an improved solution to detect, in a B-Rep having cycles of edges and modeling a part having cut-outs represented by tunnels, location of at least part of the tunnels.